package countPairs;
import java.util.*;

public class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int len = edges.length;
        int[] degree = new int[n];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            degree[edges[i][0]-1]++;
            degree[edges[i][1]-1]++;
            if(edges[i][0]>edges[i][1]) {
                int t = edges[i][0];
                edges[i][0] = edges[i][1];
                edges[i][1] = t;
            }
            map.put((edges[i][0]-1)*n+(edges[i][1]-1),map.getOrDefault((edges[i][0]-1)*n+(edges[i][1]-1),0)+1);
        } // 每个点的度数
        int[] arr = Arrays.copyOf(degree, n);
        Arrays.sort(arr);
        for (int i = 0; i < queries.length; i++) {
            int bound = queries[i],total = 0;
            for (int j = 0; j < n; j++) {
                int k = binarySearch(arr,j+1,n-1,bound - arr[j]);
                total+=n-k;
            }
            // 减去重复计算的边
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int val = entry.getKey(), freq = entry.getValue();
                int x = val / n, y = val % n;
                if (degree[x] + degree[y] > bound && degree[x] + degree[y] - freq <= bound) {
                    total--;
                }
            }
            queries[i] = total;
        }
        return queries;
    }
    private int binarySearch(int[] degree, int left, int right, int target) {
        int ans = right + 1;
        while (left<=right) {
            int mid = (left + right)>>1;
            if(degree[mid] <= target) {
                left = mid + 1;
            }else {
                right = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
}
